package problem.ej2;

import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class DistrictNetwork {

	// La red de localidades ser� modelada como un grafo
	// en donde las localidades ser�n los nodos, y los enlaces
	// entre localidades ser�n las aristas del grafo.

	// El grafo ser� representado con una matriz de adyacencias.
	// En la posicion i,j, estar� el costo de mejorar el enlace
	// entre estas dos localidades.
	private int[][] network;

	// Lista de localidades ordenadas.
	private List<Integer> localities;

	// cantidad de localidades de la red.
	private int n;

	private static final int INFINITE = Integer.MAX_VALUE;

	public DistrictNetwork(List<Integer> localities, List<Link> links) {

		this.localities = localities;
		Problem2.contador_Ej2+=2; 
		n = localities.size();
		Problem2.contador_Ej2+=2;
		this.network = new int[n][n];
		Problem2.contador_Ej2+=n;

		// Inicilizamos primero toda la matriz en 0.
		for (int i = 0; i < network.length; i++) {
			Problem2.contador_Ej2+=2;
			for (int j = 0; j < network.length; j++) {
				network[i][j] = 0;
				Problem2.contador_Ej2+=2;
			}
		}

		// Ubicamos los costos de los ejes asociados en la matriz.
		Iterator<Link> iterator = links.iterator();Problem2.contador_Ej2+=1;
		while (iterator.hasNext()) {
			Problem2.contador_Ej2+=2;

			Link link = iterator.next();
			int cost = link.getCosto();
			Problem2.contador_Ej2+=2;
			int posLoc1 = localities.indexOf(link.getLoc1());
			int posLoc2 = localities.indexOf(link.getLoc2());
			Problem2.contador_Ej2+=2;

			// Convertimos el multigrafo de nuestro problema en un grafo simple.
			// En caso de mas de un eje entre dos vertices cualquiera,
			// consideramos solo el eje de menor costo.
			if (network[posLoc1][posLoc2] == 0
					|| network[posLoc1][posLoc2] > cost) {

				network[posLoc1][posLoc2] = cost;
				network[posLoc2][posLoc1] = cost;
				Problem2.contador_Ej2+=2;
			}
		}

	}

	// Cantidad de localidades de la red.
	public int size() {
		return n;
	}

	// Encuentra el eje de menor costo, tal que tenga uno y solo un vertice en
	// el conjunto de vertices.
	public Link findMinAdjacentEdge(Set<Integer> treeLocalities) {

		Link minLink = null;
		int minLinkCost = INFINITE;
		Problem2.contador_Ej2+=1;

		int bufferedLocA = 0;
		int bufferedLocB = 0;
		Problem2.contador_Ej2+=1;

		Iterator<Integer> iterator = treeLocalities.iterator();
		Problem2.contador_Ej2+=1;

		while (iterator.hasNext()) {
			Problem2.contador_Ej2+=2;
			int locality = ((Integer) iterator.next()).intValue();
			Problem2.contador_Ej2+=2;
			for (int j = 0; j < n; j++) {
				// Si existe el eje.
				Problem2.contador_Ej2+=2;
				if (network[locality][j] != 0) {
					Problem2.contador_Ej2+=1;
					// Si la localidad es nueva.
					if (!treeLocalities.contains(new Integer(j))) {
						Problem2.contador_Ej2+=2;
						// Si encontramos un costo menor al que ya ten�amos.
						if (network[locality][j] < minLinkCost) {
							
							minLinkCost = network[locality][j];
							bufferedLocA = locality;
							bufferedLocB = j;
							Problem2.contador_Ej2+=1;
						}
					}
				}
			}

		}

		minLink = new Link(localities.get(bufferedLocA),
				localities.get(bufferedLocB), minLinkCost);
		Problem2.contador_Ej2+=1;

		return minLink;

	}

}
